The present invention relates to indexing techniques for searching computer system main memories, and more specifically, to indexing structures relating to searching of databases and arrays.
As random access memory becomes less expensive, it becomes increasingly more affordable to build computer systems with large memory systems, and in particular, large main memory systems. Within the next ten years, it may be possible to build computer systems having a terabyte of main memory serving as a buffer for a 100-terabyte database. As a result, all but the largest database tables could reside in main memory. Nevertheless, data processing performance in main memory cannot be increased indefinitely simply by increasing main memory size, even with the use of a cache memory subsystem. Therefore, it is becoming increasingly more important to improve cache memory strategy during main memory data processing operations.
Index structures are a significant factor in main memory database system performance, and can be used to reduce overall computation time without consuming very much additional memory space. In sufficiently large memory systems, most indexes can be memory resident. Indexing in main memory databases, and the performance measurements associated therewith, have been addressed in the literature, for example, in J. Lehman and Michael J. Carey, A Study of Index Structures for Main Memory Database Management Systems, Proceedings of the 12th VLDB Conference, pages 294-303, 1986, and in Kyu-Young Whang and Ravi Krishnarnurthy, Query Optimization in a Memory-Resident Domain Relational Calculus Database System, ACM Transactions on Database Systems, 15(1): 67-95, 1990, the contents of which are incorporated herein by reference. In recent years, central processor unit (CPU) speeds have increased at a much faster rate than have memory access speeds. As a result, the relative cost in time of cache misses has increased substantially. For this reason, the relative performance advantages of certain prior art indexing methods may no longer be applicable.
Another recent development relevant to the optimal selection of index structures has been the increased interest in On-Line Analytical Processing (OLAP). The respective data processing requirements of OLAP systems and of On-Line Transaction Processing (OLTP) systems are addressed in Clark D. French, xe2x80x9cOne Size Fits Allxe2x80x9d Database Architectures Do Not Work for DDS, Proceedings of the ACM SIGMOD Conference, page 449-450, 1995, and in Clark D. French, Teaching an OLTP Database Kernel Advanced Data Warehousing Techniques, Proceedings, IEEE Int""l Conf. On Data Eng., 1997, the contents of which are incorporated herein by reference. The performance of a typical OLAP system can be enhanced by improving query performance, even if at the expense of update performance. Certain commercial systems designed for such purposes include Sybase IQ, which is described in Sybase Corporation, Sybase IQ 11.2.1, 1997, the contents of which is incorporated herein by reference. OLAP system performance can be improved in this way because typical OLAP application workloads are query-intensive, but require infrequent batch updates. For example, in applications involving census data, large quantities of data is collected and updated periodically, but then remain static for relatively long periods of time. In contrast, a typical university""s data warehouse containing student records may be updated daily. Certain systems in which data remain static for relatively long periods of time presently may be on the order of several gigabytes in size, and therefore can be stored within present day main memory systems. Because updates in such systems are typically relatively infrequent and are batched, the performance associated with incremental updates of indexes in these systems may not be critical. In fact, it may even be efficient to reconstruct indexes entirely from scratch after relatively infrequent batch updates, if such an approach leads to improved query performance.
Generally speaking, the two most important criteria in selecting particular index structures are the amount of available memory space, and query performance. Because memory space normally is a critical factor in constructing main memory databases, there typically is limited space available for precomputed structures such as indexes. In addition, given a particular set of memory space constraints, the objective is to minimize the time required to perform index lookups. In main memory databases, an important factor influencing the speed of database operations is the degree of locality for the data references for the particular algorithm being run. Superior data locality leads to fewer cache misses, and therefore improved performance.
As is well known in the art, cache memories normally are fast static random access memories (RAM) that improve computer system performance by storing data likely to be accessed by the computer system. Memory references which can be satisfied by the cache are known as hits, and proceed at processor speed. Those memory references which are not found in the cache are known as misses, and result in a cache miss time penalty in the form of a fetch of the corresponding cache block from main memory. Caches are normally characterized by their capacity, block size and associativity. Capacity refers to the cache""s overall memory size; block size is the size of the basic memory unit which is transferred between cache and main memory; and associativity refers to the number of locations in the cache which are potential destinations for any single main memory address.
Typical prior art cache optimization techniques for data processing applications include clustering, compression and coloring as set forth in Trishul M. Chilimbi, James R. Larus, Mark D. Hill, Improving Pointer-Based Codes Through Cache-Conscious Data Placement, Technical Report 98, University of Wisconsin-Madison, Computer Science Department, 1998, the contents of which is incorporated herein by reference. Clustering techniques attempt to pack into a cache block data structure elements which are likely to be accessed successively. Compression attempts to remove irrelevant data from the cache and thus increase cache block utilization by enabling more usable data structure elements to be placed in the cache blocks. Compression includes key compression, structure encodings such as pointer elimination, and fluff extraction. Coloring techniques map contemporaneously-accessed data structure elements onto non-conflicting regions of the cache. Caches inherently have such conflicting regions because they have finite levels of associativity, which results in only a limited number of concurrently accessed data elements being able to be mapped to the same cache line without generating a conflict.
Certain prior art has proposed improvements in cache performance using these techniques. For example, in Michael E. Wolf, et al., A Data Locality Optimizing Algorithm, SIGPLAN Notices, 26(6):30-44, 1991, cache reference locality is exploited in an effort to improve the performance of matrix multiplication. In Anthony LaMarca, et al., The Influence of Caches on the Performance of Sorting, Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997, the effects of caches on sorting algorithms is considered, and performance was improved by restructuring these algorithms to exploit cache characteristics. In addition, there was constructed a cache-conscious heap structure which clustered and aligned heap elements with cache blocks. In Trishul M. Chilimbi, James R. Larus. and Mark D. Hill, Improving Pointer-Based Codes Through Cache-Conscious Data Placement, Technical Report 98, University of Wisconsin-Madison, Computer Science Department, 1998, it was demonstrated that cache optimization techniques can be used to improve the spatial and temporal locality of pointer-based data structures. In Chris Nyberg, et al., Alphasort: A RISC Machine Sort, Proceedings of the ACM SIGMOD Conference, pages 233-242, May 1994, it was shown that cache memory behavior should be closely considered in achieving high performance sorting. The contents of each of these references is incorporated herein by reference.
Cache conscious algorithms have also been considered in the context of database systems. For example, in Ambuj Shatdal, et al., Cache Conscious Algorithms for Relational Query Processing, Proceedings of the 20th VLDB Conference, 1994, the contents of which is incorporated herein by reference, there were suggested several approaches for improving the cache reference locality of query processing operations, such as joins and aggregations, for example. Algorithms were presented therein which provided significant performance improvements.
Although cache optimization previously has been considered in connection with tree-based structures, it has not been considered in connection with index structures used in database systems. Although certain prior art has considered the issue of compact representations of B-tree indexes, cache issues have not been considered. Examples of such prior art include F. Cesarini, et al., An Algorithm to Construct a Compact B-Tree in Case of Ordered Keys, Information Processing Letters, 17(1):1612-1630, 1983, and Wiebren De Jonge, et al., Two Access Methods Using Compact Binary Trees, IEEE Transactions on Software Engineering, 13(7):799-810, 1987, the contents of which are incorporated herein by reference.
Each type of database indexing structure known in the prior art has inherent characteristics which impact cache performance. For example, in the case of array binary searches, many accesses to elements of the sorted array may result in a cache miss. Although misses do not normally occur for the first references because of temporal locality over many searches, and also do not normally occur for the last references because of spatial locality, if many records from the array fit inside a single cache line, misses nevertheless occur for many of the intervening accesses when the array is substantially larger than the cache. In the worst case scenario, the number of cache misses is of the order of the number of key comparisons.
T-Trees have been proposed as an improved database index structure, but also exhibit cache behavior similar to that exhibited by binary searching. T-trees are balanced binary trees having many elements in a node; these elements contain adjacent key values and are stored in order. Although the objective of T-Trees is to balance the memory space overhead and the search time, T-Trees nevertheless do not optimize cache behavior or performance. Although T-Trees may initially appear to be cache conscious in that they place a greater number of keys in each node, for most T-Tree nodes only one or two end keys are actually used for purposes of comparison. As a result, the utilization of each node is relatively low. For this reason, the number of key comparisons remains the same as in a binary search, and cache behavior and performance is not improved. T-Trees are addressed in additional detail in Tobin J. Lehman and Michael J. Carey, Query Processing in Main Memory Database Management Systems, Proceedings of the ACM SIGMOD Conference, pages 239-250, 1986, and Tobin J. Lehman and Michael J. Carey, A Study of Index Structures for Main Memory Database Management Systems, Proceedings of the 12th VLDB Conference, pages 294-303, 1986, the contents of which are incorporated herein by reference.
B+-Trees and enhanced B+-Trees provide improvements in cache behavior and performance as compared to the cache performance associated with T-Trees. In B+-Trees, each internal node has stored therein internal node keys and child pointers. Record pointers, however, are stored only in leaf nodes. Multiple keys can be used to search within a node. If each node is of a size that can fit in a cache line, a single cache load can provide data capable of satisfying more than one comparison. This results in improved utilization rates for each cache line. In an OLAP environment, enhanced B+-Trees can be used to utilize all of the locations in a B+-tree node, and trees can be rebuilt whenever batch updates arrive. This approach is similar to that which was used in compact B-Trees, as discussed in F. Cesarini, et al., An Algorithm to Construct a Compact B-Tree in Case of Ordered Keys, Information Processing Letters, 17(1):1612-1630, 1983, and by the Indexed Sequential Access Method (ISAM) used in IBM""s OS/360 operating system, as discussed in Jim Gray, et al., Transaction Processing: Concepts and Techniques, The Morgan Kaufmann Publishers, San Francisco, Calif., USA, 1993. The contents of both of these references are incorporated herein by reference. In enhanced B+-Trees, node size can be designed to be exactly the same size as the cache lines, and in addition, the nodes can be aligned. Nevertheless, such enhanced B+-Trees must store child pointers within each node, which for any given node size permits only half of the node space to be used to store keys. This results in less than optimal cache behavior and performance. Although the discussion presented below addresses primarily enhanced B+-Trees, the term B+-Trees is also used to describe enhanced B+ trees.
Hash indexes can also greatly benefit from improved cache optimization. One of the most common hashing methods is known as chained bucket hashing, which is discussed in additional detail in Donald Ervin Knuth, Sorting and Searching, vol. 3 of The Art of Computer Programming, Addison-Wesley, Reading, Mass., USA, 1973, the contents of which art is incorporated herein by reference. Certain efforts have been made to improve cache performance in such hash indexing schemes. For example, in Goetz Graefe, et al., Hash Joins and Hash Teams in Microsoft SQL Server, Proceedings of the 24th VLDB Conference, pages 86-97, 1998, the contents of which is incorporated herein by reference, the cache line size was used as the bucket size. This type of approach has the potential to reduce the number of cache misses when scanning through the buckets. However, hash indexes expedite fast searching only if the length of each bucket chain is relatively small. Such an arrangement, however, requires a relatively large directory size, which in turn requires a relatively large amount of main memory space. In addition, skewed data can adversely affect hash index performance, unless the hash function is relatively sophisticated which in turn increases computation time. Further, hash indexes normally do not preserve any type of order, which in turn detracts from cache performance. In order to provide ordered access using hash indexes, an ordered list must be maintained in addition to the hash indexes.
Therefore, in view of the above-described examples and limitations in the existing art, a need has arisen for techniques to optimize cache performance in connection with index structures used in performing searches in database systems. The need has thus arisen for cache conscious indexing structures, and in particular for cache sensitive search tree indexing structures.
It is an object of the present invention to provide cache sensitive search tree (CSS-tree) index structures for providing improved searching of sorted arrays.
It is another object of the present invention to provide CSS-tree index structures which provide improved search and lookup performance as compared with conventional searching schemes.
It is yet another object of the present invention to provide CSS-tree index structures having a directory tree structure which is stored in an array and utilized as an index for a sorted array of elements.
It is still another object of the present invention to provide CSS-tree index structures having a directory tree structure containing nodes of sizes selected to correspond to the cache line size in the computer system utilizing the CSS-tree index structures.
It is a further object of the present invention to provide CSS-tree index structures having a directory tree structure containing child nodes which are located by performing arithmetic operations on array offsets.
It is yet a further object of the present invention to provide CSS-tree index structures having a directory tree structure in which memory storage requirements are reduced because it not necessary to store internal child node pointers.
It is a still further object of the present invention to provide CSS-tree index structures organized so that traversing each level in the tree yields good data reference locality, and therefore relatively few cache misses.
It is another object of the present invention to provide CSS-tree index structures which consider cache-related parameters such as reference locality and cache behavior, without requiring substantial additional amounts of memory storage.
In accordance with the present invention there are provided a search tree index system and method for locating a particular key value stored in a sorted array of key values. The system includes a computer memory for storing a search tree structure having a plurality of leaf nodes, wherein each leaf node contains multiple key values and the leaf nodes can reference the key values stored in the sorted array according to an offset value. The search tree structure stored in computer memory also has a plurality of internal nodes, wherein each internal node contains multiple key values and has associated therewith multiple children nodes. The children nodes can be referenced by the internal node associated therewith according to another offset value. The children nodes associated with each internal node can be either internal nodes or leaf nodes. The system also includes a computer processor with a cache memory characterized by a cache size, a cache line size and an associativity level. The computer processor is coupled to the computer memory to provide computational access to the sorted array of key values, the leaf nodes and the internal nodes. The computer processor determines for the key value being searched the offset value necessary to reference the children nodes from the internal nodes, and the offset value necessary to reference the key value from the leaf nodes and to locate the key value in the sorted array of key values. The quantity of internal nodes and the quantity of leaf nodes stored in the memory correspond to the characteristics of the cache memory.